package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * @author tzp
 * @since 2020/9/21
 */
public class LC516 implements DynamicProblem {
    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length() + 1];
        for (int step = 1; step <= s.length(); step++) {
            for (int start = 0; start < s.length(); start++) {
                if (start + step > s.length()) {
                    break;
                }
                if (step == 1) {
                    dp[start][step] = 1;
                } else if (step == 2) {
                    dp[start][step] = s.charAt(start) == s.charAt(start + 1) ? 2 : 1;
                } else {
                    int max = s.charAt(start) == s.charAt(start + step - 1) ?
                            dp[start + 1][step - 2] + 2 : dp[start + 1][step - 2];
                    max = Math.max(max, dp[start][step - 1]);
                    max = Math.max(max, dp[start + 1][step - 1]);
                    dp[start][step] = max;
                }
            }
        }
        return dp[0][s.length()];
    }

    public static void main(String[] args) {
        System.out.println(new LC516().longestPalindromeSubseq("bba"));
        System.out.println(new LC516().longestPalindromeSubseq("bbbab"));
    }
}
